
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include "common/functional_memoization.hpp"

unsigned int lev_helper(unsigned int m, unsigned int n, const std::string& a, const std::string& b)
{
    if (m == 0) {
        return n;
    } else if (n == 0) {
        return m;
    }

    return std::min({ lev_helper(m - 1, n, a, b) + 1,
        lev_helper(m, n - 1, a, b) + 1,
        lev_helper(m - 1, n - 1, a, b) + (a[m - 1] != b[n - 1]) });
}

unsigned int lev(const std::string& a, const std::string& b)
{
    return lev_helper(a.size(), b.size(), a, b);
}

// 递归 + 缓存版 Levenshtein 距离
unsigned int lev_cache_help(unsigned int m, unsigned int n,
    const std::string& a,
    const std::string& b,
    std::vector<std::vector<int>>& cache)
{
    // 如果已经计算过，直接返回缓存值
    if (cache[m][n] != -1)
        return cache[m][n];

    // 边界条件
    if (m == 0)
        return cache[m][n] = n;
    if (n == 0)
        return cache[m][n] = m;

    // 递归计算并写入缓存
    cache[m][n] = std::min({
        lev_cache_help(m - 1, n, a, b, cache) + 1, // 删除
        lev_cache_help(m, n - 1, a, b, cache) + 1, // 插入
        lev_cache_help(m - 1, n - 1, a, b, cache) + (a[m - 1] != b[n - 1]) // 替换/匹配
    });

    return cache[m][n];
}

unsigned int lev_cache(const std::string& a, const std::string& b)
{
    unsigned int m = a.size();
    unsigned int n = b.size();

    // 初始化缓存矩阵，-1 表示“未计算”
    std::vector<std::vector<int>> cache(m + 1, std::vector<int>(n + 1, -1));

    return lev_cache_help(m, n, a, b, cache);
}

int main()
{
    std::vector<std::pair<std::string, std::string>> tests = {
        { "example", "exam" },
        { "kitten", "sitting" },
        { "flaw", "lawn" },
        { "", "abc" },
        { "abc", "" }
    };

    auto generalized_lev = functional_memoization(lev);

    for (auto& [a, b] : tests) {
        std::cout << a << " vs " << b
                  << " → plain: " << lev(a, b)
                  << " → general cached: " << generalized_lev(a, b)
                  << ", cache: " << lev_cache(a, b) << '\n';
    }
}
